//: [Previous](@previous)
/*:
 #28 [Implement strStr()](https://leetcode.com/problems/implement-strstr/description/)
 
 查找子串
 
 Implement strStr().
 
 Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
 
 Example 1:
 
 Input: haystack = "hello", needle = "ll"
 Output: 2
 Example 2:
 
 Input: haystack = "aaaaa", needle = "bba"
 Output: -1
 Clarification:
 
 What should we return when needle is an empty string? This is a great question to ask during an interview.
 
 For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
 */
import Foundation

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if haystack.count < needle.count {
            return -1
        }
        
        if needle.count == 0 {
            return 0
        }
        
        for i in 0...(haystack.count - needle.count) {
            var j = 0
            
            while j < needle.count {
                if haystack[i+j] != needle[j] {
                    break;
                }
                j+=1
            }
            
            if j == needle.count {
                return i
            }
        }
        return -1
    }
    
    /// KMP算法 T= 0(n+p)
    func strStr_KMP(_ haystack: String, _ needle: String) -> Int {
        if haystack.count < needle.count {
            return -1
        }
        
        if needle.count == 0 {
            return 0
        }
        
        let arr: [Character] = Array((needle))
        var next: [Int] = makeNext(arr)
        
        var i = 0, j = 0
        while i < haystack.count && j < needle.count {
            
            if j == -1 || haystack[i] == needle[j] { // P 的第一个字符不匹配或 S[i] == P[j]
                i += 1
                j += 1
            } else {
                j = next[j]
            }
        }
        
        if j == needle.count { // 匹配成功
            return i - j
        }
        
        return -1
    }
    func makeNext(_ arr: [Character]) -> [Int] {
        var next: [Int] = [Int](repeating: -1, count: arr.count)
        var j = 0
        var k = -1
        
        while j < arr.count - 1 {
            if k == -1 || arr[j] == arr[k] {
                j += 1
                k += 1
                next[j] = k
                
                if arr[j] != arr[k] {
                    next[j] = k
                } else {
                    next[j] = next[k] // 既然相同就继续往前找真前缀
                }
                
            } else {
                k = next[k]
            }
        }
        return next
    }
    
    func strStr_index(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }
        
        let distance = haystack.count - needle.count
        for i in 0...distance {
            let start = haystack.index(haystack.startIndex, offsetBy: i)
            let end = haystack.index(haystack.startIndex, offsetBy: i+needle.count)
            
            if haystack[start..<end] == needle {
                return start.encodedOffset
            }
        }
        return -1
    }
}

print(Solution().strStr("hello", "ll"))
print(Solution().strStr("abcdefghkkads", "abcdefghj"))

print(Solution().strStr_KMP("hello", "ll"))


//: [Next](@next)
